"""
https://leetcode.cn/problems/climbing-stairs/description/?envType=study-plan-v2&envId=dynamic-programming

70. 爬楼梯
简单
相关标签
相关企业
提示
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？



示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶


提示：

1 <= n <= 45
"""
import time
import timeit


class Solution:
    def climbStairs(self, n: int) -> int:
        zuhe1 = [[1]]
        zuhe2 = [[1, 1], [2]]

        t1 = 1
        t2 = 2
        if n == 1:
            # self.print_zuhe(zuhe1)
            return 1
        elif n == 2:
            # self.print_zuhe(zuhe2)
            return 2

        for i in range(3, n + 1):
            p = t2
            t2 = p + t1
            t1 = p
            """
            import copy
            zuhetmp = copy.deepcopy(zuhe2)
            for e in zuhe2:
                e.append(1)
            for e in zuhe1:
                e.append(2)
            zuhe2 += zuhe1
            zuhe1 = zuhetmp
            """

        # self.print_zuhe(zuhe2)
        # print(f'len(zuhe2)=',len(zuhe2))
        return t2

    def print_zuhe(self, zuhe):
        for e in zuhe:
            print(e)


#官方解法
class Solution2:
    def climbStairs(self, n: int) -> int:
        q = [[1, 1], [1, 0]]
        res = self.matrix_pow(q, n)
        return res[0][0]

    def matrix_pow(self, a, n):
        ret = [[1, 0], [0, 1]]  # 单位矩阵
        while n > 0:
            if n & 1:
                ret = self.multiply(ret, a)
            n >>= 1
            a = self.multiply(a, a)
        return ret

    def multiply(self, a, b):
        c = [[0] * 2 for _ in range(2)]
        for i in range(2):
            for j in range(2):
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
        return c


#微秒

if __name__ == '__main__':
    solution = Solution()
    solution2 = Solution2()
    # res=solution.climbStairs(5)
    # print(res)
    # for i in range(10000, 10010):
    for i in range(1, 10):
        res = solution.climbStairs(i)
        #耗时高点
        print(i, '-----', res, '动态规划算法')
        #耗时低
        res = solution2.climbStairs(i)
        print(i, '-----', res, '矩阵快速幂算法耗时')

        """
        start_time = time.time()
        res = solution.climbStairs(i)
        end_time = time.time()
        elapsed_milliseconds = int((end_time - start_time) * 1000)
        print(i, '-----', res, '动态规划算法耗时:', {elapsed_milliseconds}, 'ms')
        start_time = time.time()
        res = solution2.climbStairs(i)
        end_time = time.time()
        elapsed_milliseconds = int((end_time - start_time) * 1000)
        print(i, '-----', res, '矩阵快速幂算法耗时:', {elapsed_milliseconds}, 'ms')
        """

"""
解答:
  n=1和n=2使用固定的答案
  --------- n=1 --------- 
  1
  --------- n=2 --------- 
  1+1
  2
  
  n=3的组合是 n=1组合中所有元素 +2  n=2组合中所有元素+1  连个组合合并之后就是 n=3 的答案
  按照这个逻辑,所以 dp[n] = dp[n - 1] + dp[n - 2] 
  所有需要从3开始循环到 n 为止
  
  相当于最后一个台阶如果是 爬 1 个台阶,那就是在 dp[n-1] 的组合中每个方案都爬1个台阶
  最后一个台阶如果是 爬 2 个台阶,那就是在 dp[n-2] 的组合中每个方案都爬2个台阶
  
  
"""
